#include<iostream>
#include<vector>
using namespace std;


class Solution {
public:
    int ans = -1;
    int flag = 0;
    void _search(vector<int>& nums, int target, int begin, int end) {
        if (begin > end || flag)
            return;
        int mid = (begin + end) / 2;
        if (nums[mid] == target) {
            ans = mid;
            flag = 1;
            return;
        }
        int left, right;
        if (nums[begin] > nums[end] && nums[mid] < nums[end]) {
            _search(nums, target, begin, mid - 1);
            if (target < nums[mid] || target > nums[end])
                return;
            left = mid + 1, right = end;
        }
        else if (nums[begin] > nums[end] && nums[mid] > nums[end]) {
            _search(nums, target, mid + 1, end);
            if (target > nums[mid] || target < nums[begin])
                return;
            left = begin, right = mid - 1;
        }
        else {
            left = begin, right = end;
        }
        while (left <= right) {
            int tmpMid = (left + right) / 2;
            if (nums[tmpMid] > target)
                right = tmpMid - 1;
            else if (nums[tmpMid] < target)
                left = tmpMid + 1;
            else {
                ans = tmpMid;
                flag = 1;
                return;
            }
        }
    }

    int search(vector<int>& nums, int target) {
        _search(nums, target, 0, nums.size() - 1);
        return ans;
    }
};